#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <set>
#include <map>
using namespace std;
/*---------------------set&&multiset的使用---------------------*/
//int main()
//{
//	//去重+升序排序
//	//set<int> s;
//	//去重+降序排序(给一个大于的仿函数)
//	set<int, greater<int>> s;
//	s.insert(2);
//	s.insert(7);
//	s.insert(4);
//	s.insert(7);
//	set<int>::iterator it = s.begin();
//	while (it != s.end())
//	{
//		cout << *it << " ";
//		it++;
//		//set是不允许修改的,因为set底层是搜索树,搜索树修改了以后
//		//会导致这棵树出问题
//	}
//	cout << endl;
//	//插入一段initializer_list的值
//	s.insert({ 2,8,3,9 });
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//	//插入string类型的值
//	set<string> strset = { "sort","insert","add" };
//	for (auto e : strset)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//	return 0;
//}

//int main()
//{
//	set<int> s = { 4,2,7,2,8,5,9 };
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//	//删除最小值,直接给begin就可以删除,如果删除最大就得end-1。
//	s.erase(s.begin());
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//	//直接删除x
//	int x = 0;
//	cin >> x;
//	int num = s.erase(x);
//	if (!num)
//	{
//		cout << x << "不存在" << endl;
//	}
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//	//直接查找再利用迭代器删除x
//	cin >> x;
//	auto pos = s.find(x);
//	if (pos != s.end())
//	{
//		s.erase(pos);
//	}
//	else
//	{
//		cout << x << "不存在" << endl;
//	}
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//	return 0;
//}
//int main()
//{
//	set<int> s = { 1,2,3,4,5,6,7,8,9 };
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//	int x = 0;
//	//算法库的查找O(N)
//	auto pos1 = find(s.begin(), s.end(), x);
//	//set自身实现的查找O(logN)
//	auto pos2 = s.find(x);
//	//利用count间接实现快速查找
//  //count的作用就是去计算一个数据到底有几个。有的话就是1个,没的话就是0个。
//	cin >> x;
//	if (s.count(x))
//	{
//		cout << x << "在!" << endl;
//	}
//	else
//	{
//		cout << x << "不存在!" << endl;
//	}
//	return 0;
//}

/*
	而我们的find有两种find,第一种就是set中的find，第二种方式
	可以调算法库的find,这个时候我们就可以发现vector,list包括
	deque这些容器都没有设计find,都用的是算法库里面的,而我们这
	里的set又自己设计了一个find,那么这两个有没有差别呢?
	其实这两个有很大的差别,结果上都一样,但是过程上有很大的差别,
	set中的find是比它大就往右走,比它小就往左走,做高查找高度次,
	平衡二叉树,高度能控制再logn,也就是说1000个数大概找十次,
	1000000万个数大概找20次,但是算法库的find的可不一样,虽然是
	搜索树,但是这个算法是通用型的算法,不仅仅是针对某个容器,是针对
	所有容器的,都是暴力查找,把一整个容器遍历一边再查找,时间复杂度
	是O(N),这是很坑的,虽然说set可以用它,但是实践当中是不会用的
*/


//int main()
//{
//	set<int> s1({ 1,2,3,4,5  });
//	set<int> s2({ 6,7,8,9,10 });
//	for (auto e : s1)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//	for (auto e : s2)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//	s1.swap(s2);
//	for (auto e : s1)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//	for (auto e : s2)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//	return 0;
//}

/*
有的容器也自身提供了一个swap,比如set,vector,list容器这些要进行交换
的时候,如果我们使用算法库中创建中间变量来交换的算法的话,深拷贝的交
换代价实在太大,所以说容器都会提供一个自己的swap,只交换底层的内部结
构,如果是两颗搜索树,我们交换根就可以了。
*/

//int main()
//{
//	set<int> s = { 1,3,5,8,9 };
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//	int x = 0;
//	cin >> x;
//	if (s.count(x))
//	{
//		cout << x << "存在" << endl;
//	}
//	else
//	{
//		cout << x << "不存在" << endl;
//	}
//	return 0;
//}

//int main()
//{
//	set<int> s;
//	for (int i = 1; i < 10; i++)
//		s.insert(i * 10);
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//	//实现查找到的[itlow,itup)包含[30, 60]区间
//	//返回>=30
//	auto itlow = s.lower_bound(30);
//	//返回>60
//	auto itup = s.upper_bound(60);
//	//删除这段区间的值
//	s.erase(itlow, itup);
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//	return 0;
//}

/*
假设找30~60这段区间的值,如果没有30这个值应该怎么办,所以我们应该
找>=30的,这样的话有30就返回30,没有30的话就返回比30大的第一个值
第二个要返回60,但是要注意一个点,C++STL中有个特点,凡是设计迭代器
区间有一个要求,这个要求就是必须要给左闭右开,所以要找60的话就不能
返回60,上面的例子,有60就返回70,没有60还是返回的70,所以右边区间的值
不能包含60,得是比60大的值。
所以lower_bound和upper_bound完美解决了这个问题
lower_bound是找大于等于传入的值的
upper_bound是找大于传入的值的
*/



//int main()
//{
//	//相比set不同的是,multiset是排序,而不是去重。
//	multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 };
//	auto it = s.begin();
//	while (it != s.end())
//	{
//		cout << *it << " ";
//		++it;
//	}
//	cout << endl;
//
//	//相比set不同的是,x可能会存在多个,find查找的是中序的第一个
//	int x = 0;
//	cin >> x;
//	auto pos = s.find(x);
//	while (pos != s.end() && *pos == x)
//	{
//		cout << *pos << " ";
//		pos++;
//	}
//	cout << endl;
//	//相比set不同的是,count会返回x的实际个数
//	cout << s.count(x) << endl;
//	//相比set不同的是，erase给值时会删除所有的x
//	s.erase(x);
//	for (auto e : s)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//	return 0;
//}

/*---------------------map&&multimap的使用---------------------*/
//#include <map>
//int main()
//{
//	pair<string, string> lv1 = { "left","左边" };
//	//initializer_list的构造以及迭代器遍历
//	/*
//	这里的initializer_list有双重的转换,这里的initializer_list是一个
//	value_type,这个value_type是pair类型,相等于是pair的initializer_list
//	pair这种多参数的也支持这种{}的隐式类型转换,单参数是直接转换,
//	多参数是先走pair的构造,
//	*/
//	map<string, string> dict = { {"left","左边"},{"right","右边"},{"up","上面"},{"down","下面"} };
//	//map<string, string>::iterator it = dict.begin();
//	auto it = dict.begin();
//	while (it != dict.end())
//	{
//		//cout << *it << " ";
//		//这样编不过去,因为pair没有支持流插入,
//		//cout << (*it).first << ":" << (*it).second << endl;
//		//cout << it->first << ":" << it->second << endl;
//		cout << it.operator->()->first << ":" << it.operator->()->second << endl;
//		it++;
//	}
//	cout << endl;
//
//	//insert插入pair对象的四种方式,最后一种最方便
//	//1.插入pair对象
//	pair<string, string> kv1("first","第一个" );
//	dict.insert(kv1);
//	//2.插入匿名对象
//	dict.insert(pair<string, string>({"second","第二个"}));
//	//3.make_pair插入,make_pair是一个函数模板,本质还是调用pair匿名对象,相等于
//	//套了一层,调用make_pair就不用去声明模板参数,而是让它去推导,而且还是inline，
//	//再底层展开是等价的,
//	dict.insert(make_pair("sort", "排序"));
//	//4.C++11支持隐式类型转换
//	dict.insert({ "auto","自动的" });
//
//	//范围for遍历
//	/*
//	加上引用可以减少拷贝,替换上面的代码就是把*it给e,那么就是pair
//	类型,里面有两个参数,这里就会很坑的
//	*/
//	for (const auto& e : dict)
//	{
//		cout << e.first << ":" << e.second << endl;
//	}
//	cout << endl;
//	//C++17支持结构化绑定,结构化绑定再其他地方
//	//用处不大,但是在遍历map的时候很有用,因为
//	//map里面有多个数据
//	for (const auto& [k, v] : dict)
//	{
//		cout << k << ":" << v << endl;
//	}
//	return 0;
//}


//#include <map>
//int main()
//{
//	map<string, string> dict = { {"left","左边"},{"right","右边"},{"up","上面"},{"down","下面"} };
//	pair<string, string> kv1("first","第一个" );
//	dict.insert(kv1);
//	dict.insert(pair<string, string>({"second","第二个"}));
//	dict.insert(make_pair("sort", "排序"));
//	dict.insert({ "auto","自动的" });
//	auto it = dict.begin();
//	while (it != dict.end())
//	{
//		cout << it->first << ":" << it->second << endl;
//		it->first += 'x';//first是const的,不能修改,Key不能修改
//		it->second += 'x';
//		++it;
//	}
//	it = dict.begin();
//	while (it != dict.end())
//	{
//		cout << it->first << ":" << it->second << endl;
//		++it;
//	}
//	string str;
//	while (cin >> str)
//	{
//		auto ret = dict.find(str);
//		if (ret != dict.end())
//		{
//			cout << "->" << ret->second << endl;
//		}
//		else
//		{
//			cout << "无此单词,请重新输入" << endl;
//		}
//	}
//	return 0;
//}

//#include <map>
//int main()
//{
//	map<string, string> dict = { {"left","左边"},{"right","右边"},{"up","上面"},{"down","下面"} };
//	pair<string, string> kv1("first","第一个" );
//	dict.insert(kv1);
//	dict.insert(pair<string, string>({"second","第二个"}));
//	dict.insert(make_pair("sort", "排序"));
//	dict.insert({ "auto","自动的" });
//	auto it = dict.begin();
//	while (it != dict.end())
//	{
//		cout << it->first << ":" << it->second << endl;
//		++it;
//	}
//	string str;
//	cin >> str;
//	auto ret = dict.find(str);
//	if (ret != dict.end())
//	{
//		dict.erase(ret);
//	}
//	else
//	{
//		cout << "无此单词,请重新输入" << endl;
//	}
//	for (const auto& e : dict)
//	{
//		cout << e.first << ":" << e.second << endl;
//	}
//	cout << endl;
//	return 0;
//}


//#include<iostream>
//#include<map>
//#include<string>
//using namespace std;
//int main()
//{
//	// 利⽤find和iterator修改功能，统计⽔果出现的次数
//	string arr[] = { "苹果", "西⽠", "苹果", "西⽠", "苹果", "苹果", "西⽠",
//	"苹果", "⾹蕉", "苹果", "⾹蕉" };
//	map<string, int> countMap;
//	for (const auto& str : arr)
//	{
//		// 先查找⽔果在不在map中
//		// 1、不在，说明⽔果第⼀次出现，则插⼊{⽔果, 1}
//		// 2、在，则查找到的节点中⽔果对应的次数++
//		auto ret = countMap.find(str);
//		if (ret == countMap.end())
//		{
//			countMap.insert({ str, 1 });
//		}
//		else
//		{
//			ret->second++;
//		}
//	}
//	for (const auto& e : countMap)
//	{
//		cout << e.first << ":" << e.second << endl;
//	}
//	cout << endl;
//	return 0;
//}

//#include<iostream>
//#include<map>
//#include<string>
//using namespace std;
//int main()
//{
//	// 利⽤[]插⼊+修改功能，巧妙实现统计⽔果出现的次数
//	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
//	"苹果", "香蕉", "苹果", "香蕉" };
//	map<string, int> countMap;
//	for (const auto& str : arr)
//	{
//		// []先查找⽔果在不在map中
//		// 1、不在，说明水果第⼀次出现，则插入{水果, 0}，同时返回次数的引⽤，++一下就变成1次了
//		// 2、在，则返回水果对应的次数++
//		countMap[str]++;
//	}
//	for (const auto& e : countMap)
//	{
//		cout << e.first << ":" << e.second << endl;
//	}
//	cout << endl;
//	return 0;
//}


//#include<iostream>
//#include<map>
//#include<string>
//using namespace std;
//int main()
//{
//	map<string, string> dict;
//	dict.insert(make_pair("sort", "排序"));
//	// key不存在->插入 {"insert", string()}
//	dict["insert"];
//	// 插入+修改
//	dict["left"] = "左边";
//	// 修改
//	dict["left"] = "左边、剩余";
//	// key存在->查找
//	cout << dict["left"] << endl;
//	return 0;
//}


/*
我们直接可以用map,map的key是一个节点,也就是原节点,map的value也是一个节点,是拷贝节点
map是一个key,value模型,我们可以把任意两个毫不相关的值因为需要建立关系,而且快速查找
也就是说原链表中有一个7,那么就创建一个7,然后插入到map当中,原链表中有一个13,那么就创建
一个13节点,然后再插入到map当中,也就意味着再进行深拷贝的同时不用插到原链表的后面,深拷贝
这个原链表的时候就把他们链接在一起了,链接在一起之后再把原节点和拷贝节点建立出一个链接
关系,建立出链接关系之后要控制random,第一个节点的random指向空,那么拷贝节点的random也指
向空,原链表的第二个节点的random指向7,那么拷贝节点也能找到对应的那个7,用原链表的7作为key,
[]就可以找到对应的value,或者用find也可以,然后以此类推,
*/

/*
出现次数最多的前k个,第一种方法可以用排序,第二种方法可以用堆,但是这道题
中返回的答案应该按单词出现频率由高到低排序,如果不同的单词有相同出现
的频率,按字典顺序排序,就是按ASCII码值排序,其实就是按string的比较方式,
那么我们可以用sort,但是sort不能对map进行排序,因为sort对迭代器也是有要求的
要求是随机访问的迭代器,而map是一个双向迭代器,不符合要求的,否则会报错,
string,vector,deque,只有这几个容器才是随机迭代器,所以把这些数据导入到vector
中才能用sort进行排序
*/

#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <queue>
class Solution {
public:
	struct Compare
	{
		bool operator()(const pair<string, int>& x, const pair<string, int>& y)
			const
		{
			return x.second > y.second || (x.second == y.second && x.first <
				y.first);;
		}
	};
	vector<string> topKFrequent(vector<string>& words, int k) {
		map<string, int> countMap;
		for (auto& e : words)
		{
			countMap[e]++;
		}
		vector<pair<string, int>> v(countMap.begin(), countMap.end());
		// 仿函数控制降序,仿函数控制次数相等，字典序⼩的在前⾯
		sort(v.begin(), v.end(), Compare());
		// 取前k个
		vector<string> strV;
		for (int i = 0; i < k; ++i)
		{
			strV.push_back(v[i].first);
		}
		return strV;
	}
};
class Solution {
public:
	struct Compare
	{
		bool operator()(const pair<string, int>& x, const pair<string, int>& y)
			const
		{
			// 要注意优先级队列底层是反的，⼤堆要实现⼩于⽐较，所以这⾥次数相等，想要字典
			//序⼩的在前⾯要⽐较字典序⼤的为真
			return x.second < y.second || (x.second == y.second && x.first >
				y.first);
		}
	};
	vector<string> topKFrequent(vector<string>& words, int k) {
		map<string, int> countMap;
		for (auto& e : words)
		{
			countMap[e]++;
		}
		//将map中的<单词，次数>放到priority_queue中，仿函数控制⼤堆，次数相同按照字典
		//序规则排序
		priority_queue<pair<string, int>, vector<pair<string, int>>, Compare>
			p(countMap.begin(), countMap.end());
		vector<string> strV;
		for (int i = 0; i < k; ++i)
		{
			strV.push_back(p.top().first);
			p.pop();
		}
		return strV;
	}
};

